//给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换
//需遵循如下规则： 
//
// 
// 每次转换只能改变一个字母。 
// 转换后得到的单词必须是字典中的单词。 
// 
//
// 说明: 
//
// 
// 如果不存在这样的转换序列，返回一个空列表。 
// 所有单词具有相同的长度。 
// 所有单词只由小写字母组成。 
// 字典中不存在重复的单词。 
// 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 
// 
//
// 示例 1: 
//
// 输入:
//beginWord = "hit",
//endWord = "cog",
//wordList = ["hot","dot","dog","lot","log","cog"]
//
//输出:
//[
//  ["hit","hot","dot","dog","cog"],
//  ["hit","hot","lot","log","cog"]
//]
// 
//
// 示例 2: 
//
// 输入:
//beginWord = "hit"
//endWord = "cog"
//wordList = ["hot","dot","dog","lot","log"]
//
//输出: []
//
//解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。 
// Related Topics 广度优先搜索 数组 字符串 回溯算法 
// 👍 318 👎 0

package leetcode.editor.cn;

import java.util.*;

//Java：单词接龙 II
public class P126WordLadderIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     *
     * 思路：三个步骤：
     *      1. 构造图，单词作为点。遍历词典，两两比较，若能够通过一个字母直接转换的，便是图的相邻的点。
     *      2. 广度遍历，得到最短的转换序列的长度 min
     *      3. 深度遍历，得到在min个长度之内的序列。
     *      注：要存储一个next数组，存每一层的单词，不然的话，在深度遍历的时候，会因为递归太深，导致内存超出限制
     *
     * 执行用时： 904 ms , 在所有 Java 提交中击败了 9.63% 的用户 内存消耗： 44.6 MB , 在所有 Java 提交中击败了 68.79% 的用户
     *
     */
    class Solution {
        private List<List<String>> list = new ArrayList<>();
        private Map<String, Set<String>> graph;     // 图
        private Map<Integer, Set<String>> next = new HashMap<>();      // path.size() 这一层应该遍历的单词

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            // 将开始单词也加入到单词表中
            if (!wordList.contains(beginWord)) {
                wordList.add(beginWord);
            }

            graph = createGraph(wordList);
            int level = bfs(beginWord, endWord);
            if (level != -1) {
                Stack<String> path = new Stack<>();
                path.add(beginWord);
                dfs(beginWord, endWord, level, path);
            }
            return list;
        }

        /**
         * 深度优先遍历
         */
        private void dfs(String word, String target, int min, Stack<String> path) {
            Set<String> neighbor = graph.get(word);
            if (neighbor == null) {
                return;
            }
            if (word.equals(target)) {
                list.add(new ArrayList<>(path));
                return;
            } else {
                if (path.size() >= min) {
                    return;
                }
            }

            for (String str : neighbor) {
                // 只遍历本层的单词
                if (path.contains(str) || !next.get(path.size()).contains(str)) {
                    continue;
                }
                path.push(str);
                dfs(str, target, min, path);
                path.pop();
            }
        }

        /**
         * 广度优先遍历，返回最短查询到的次数，查不到的话 返回-1
         */
        private int bfs(String start, String end) {
            int level = 0;
            Set<String> visit = new HashSet<>();    // 已经访问过的
            Queue<String> deque = new ArrayDeque<>();
            deque.add(start);
            visit.add(start);
            while (!deque.isEmpty()) {
                int size = deque.size();
                next.put(level + 1, new HashSet<>());
                for (int i = 0; i < size; i++) {
                    String str = deque.poll();
                    if (end.equals(str)) {
                        return level + 1;
                    }
                    if(graph.get(str) == null){
                        return -1;
                    }

                    for (String word : graph.get(str)) {
                        if (visit.contains(word)) {
                            continue;
                        }
                        visit.add(word);
                        deque.add(word);
                        next.get(level + 1).add(word);
                    }
                }
                level++;
            }
            return -1;
        }

        // 建图
        private Map<String, Set<String>> createGraph(List<String> wordList) {
            Map<String, Set<String>> map = new HashMap<>();
            for (int i = 0; i < wordList.size(); i++) {
                String a = wordList.get(i);
                for (int k = i + 1; k < wordList.size(); k++) {
                    String b = wordList.get(k);
                    if (isNeighbor(a, b)) {
                        if (map.get(a) == null) {
                            map.put(a, new HashSet<>());
                        }
                        if (map.get(b) == null) {
                            map.put(b, new HashSet<>());
                        }
                        map.get(a).add(b);
                        map.get(b).add(a);
                    }
                }
            }
            return map;
        }

        // 是否邻居[可以通过一个字母直接转换]
        private boolean isNeighbor(String a, String b) {
            int diff = 0;
            for (int i = 0; i < a.length() && diff <= 1; i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    diff++;
                }
            }
            return diff == 1;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
//        String s1 = "qa";
//        String s2 = "sq";
//        String[] nums = new String[]{
//                "si", "go", "se", "cm", "so", "ph", "mt", "db", "mb", "sb", "kr", "ln", "tm", "le", "av", "sm", "ar", "ci", "ca", "br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya", "cr", "po", "fe", "ho", "ma", "re", "or", "rn", "au", "ur", "rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if", "pb", "ge", "th", "pm", "rb", "sh", "co", "ga", "li", "ha", "hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh", "wm", "an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn", "mi", "am", "ex", "pt", "io", "be", "fm", "ta", "tb", "ni", "mr", "pa", "he", "lr", "sq", "ye"
//        };
        String s1 = "hot";
        String s2 = "hog";
        String[] nums = new String[]{
                "hot", "hog"
        };
        List<String> words = Arrays.asList(nums);
        Solution solution = new P126WordLadderIi().new Solution();
        System.out.println(solution.findLadders(s1, s2, words));
        // TO TEST
    }

}